Integrated circuit technology has reduced the cost of electronic systems to the point where almost any member of the public can now, for example, own a computer that has capabilities which could have been found only in the largest industrial and military laboratories a short twenty years ago. The trend towards reduced size, reduced cost and the placement of more and more components on a single chip has continued unabated. VLSI (Very Large Scale Integration) is the current term used to describe such very dense integrated circuits. The present invention relates to the creation of VLSI circuits.
One of the major problems in the VLSI technology is the following: given the logical design of a circuit, how can the components and/or circuit modules be best positioned to minimize the unused areas and the areas devoted to the interconnections between the modules. The primary purpose of this minimization is to enable the placement of as many instances of the chip as possible on a single semiconductor wafer, thereby reducing fabrication costs. Alternatively, such minimization permits the placement of more computing power on a given chip size, and thereby also deriving performance and cost advantages. Another purpose is to reduce the path lengths in the circuit and the consequent delays and thus increase the speed of operation. One variant of this problem is the layout of a circuit made up of standardized circuit cells, or "polycells," which can be laid out in rows. Common signals such as power, ground and clocks are then routed through busses within the rows of cells. Terminals at the top and bottom of each cell are used to connect the cells to each other by conductive paths in the channels between the rows of cells. The use of polycells in designing the layout or a circuit offers the advantage of relatively fast turn-around time for the design.
One approach to the placement of circuit modules on an integrated circuit substrate was disclosed in U.S. Pat. No. 3,617,714, granted Nov. 2, 1971 to B. W. Kernighan and S. Lin, and assigned to applicant's assignee. In this patent, the modules and their interconnections are treated as the vertices and edges, respectively, of a graph. Optimum, or near optimum, partition of the vertices of the graph are obtained by creating an arbitrary partition and then iteratively exchanging pairs or groups of vertices to find a better partition, i.e., a partition with fewer inter-partition edges. Once partitioned, each subset is itself partitioned, and so forth, until the relative positions of all of the circuit modules are closely circumscribed. Various other techniques for identifying clusters (called partitioning, nested bisection, and min-cut placement) are described, for example, in the following references:
1. U. Lauther, "A Min-Cut Placement Algorithm for General Cell Assemblies Based on Graph Partitioning,"Proc. 16th Design Automation Workshop (June, 1979); PA1 2. M. Goldberg and M. Burstein, "Heuristic Improvement Technique for Bisection of VLSI Networks", International Conference on Computer Design (1983); PA1 3. D. C. Schmidt and L. E. Druffel, "An Iterative Algorithm for Placement and Assignment of Integrated Circuits," Proc. 12th Design Automation Workshop (1975); PA1 4. L. I. Corrigan, "A Placement Capability Based on Partitioning," Proc. 16th Design Automation Workshop (1979); and PA1 5. M. A. Breuer, "Min-Cut Placement" J. Design Automation & Fault Tolerant Computing 1(4) pp. 343-362 (October, 1977).
Each of these techniques requires the logical interconnectivity of the circuit to be represented by a graph, with the components as nodes and the interconnections as edges.
The above-mentioned Kernighan-Lin technique can be used advantageously to identify clusters of circuit components or polycells that ought to be placed close to each other. Unfortunately, other constraints on the placement of circuit modules must also be observed in any real placement of modules on integrated circuit chips. One such major constraint is the placement of terminals and the other integrated circuit modules, i.e., connectivity constraints outside of the placement sub-area. Obviously, a component layout which does not take such external module placement constraints into account will be subject to significant placement errors which either must be corrected or else suffer the resulting increase in interconnection lengths. Indeed, any scheme which attempts to modify an optimized placement after the placement is selected so as to account for constraints like the terminals of external module placement runs the risk of losing any advantage thereby gained.
Solution to this problem is disclosed in U.S. Pat. No. 4,577,276 granted Mar. 18, 1986 to A. E. Dunlop and B. W. Kernigham and assigned to applicant's assignee. In this patent, the positions of the external connections to an integrated circuit module are utilized at the beginning in selecting optimum or near optimum placements of modules on the integrated circuit substrate. Thereafter, on successive iterations, network connection terminals having position-sensitive placement constraints outside the placement area are likewise integrated into the placement strategy. This technique is called "terminal propagation," since the position of the "terminal" (outside placement constraint) "propagates" throughout the placement procedure, insuring a final placement which takes these outside placement constraints into account.
More particularly, the outside placement constraint is identified as an area boundary crossing whose position on the edge of the area reflects the outside constraint. The terminal propagation property is obtained by computing a rectilinear Steiner tree on the terminals outside the area being partitioned. The Steiner tree edges create the boundary crossings used for identifying the outside placement constraints. For most effective realization of the process, Dulop et al suggest the use of a programmed general purpose digital computer, and to that end they disclose a pseudocode for implementing the method.
The Dunlop et al disclosure permits an efficient placement of circuit elements that are position sensitive by the use of the terminal propagation technique, but the area that Dunlop et al consider for placing the circuit elements is rectangular. Alas, the chips to be designed quite commonly contain large circuit blocks, or macro cells, such as ROMs, RAMs, PLAs, etc., in addition to thousands of interconnected cells of "standard" or custom designs. Since the design and layout of such macro cells has been previously accomplished and honed to perfection (hopefully), it makes most sense to simply place the previously designed macro cells at convenient locations within the chip layout and then proceed with the layout of the remaining cells. However, when the macro cells are placed on the chip, the resulting available area is no longer rectangular. The natural thing to do (and prior art designs seem to bear this out), is to manually place the macro cells at the corners of the chip or close to one edge, so that the remaining available area is most compact and as close to being rectangular as possible. Thereafter, the remaining area is manually divided to form a set of rectangular areas and the circuitry is allocated to the divided portions. Detailed (and perhaps automatic) layout of the circuitry assigned to each of the divided subareas follows. Thus, typically, a circuit to be laid out is divided into macro cells and polycells. The polycells are manually divided into several groups using the designer's knowledge of the interconnectivity of the polycells, with the number of the groups being dependent on the number of rectangular areas that are left on the chip after manual placement of the macro cells. The number of polycells assigned to each group is estimated by the designer and then the polycells are placed within the floor plan using known placement methods. If the selected polycell division turns out a poor floor plan, then the process must be repeated. Indeed, even when the result is within the bounds of the available chip area, one does not know whether an optimum layout was achieved. What is even more disturbing is that presently macro cells are placed along the IC edges in order to reduce the layout burden, but such placement almost assures a non-optimum layout, because access to chip I/O pads is blocked by the macro cells.
No automated procedure seems to be available that permits both freedom in placement of the macro cells and optimized allocation of the remaining circuitry to the available non-rectangular area.